In Matroid, a binary matroid is a matroid that can be represented over the finite field GF(2).[.] That is, up to isomorphism, they are the matroids whose elements are the columns of a Logical matrix and whose sets of elements are independent if and only if the corresponding columns are linearly independent in GF(2).
Alternative characterizations
A matroid
is binary if and only if
-
It is the matroid defined from a symmetric matrix (0,1)-matrix.
[.]
-
For every set of circuits of the matroid, the symmetric difference of the circuits in can be represented as a disjoint union of circuits.
[.][, Theorem 10.1.3, p. 162.]
-
For every pair of circuits of the matroid, their symmetric difference contains another circuit.
-
For every pair where is a circuit of and is a circuit of the dual matroid of , is an even number.
[.]
-
For every pair where is a basis of and is a circuit of , is the symmetric difference of the fundamental circuits induced in by the elements of .
-
No matroid minor of is the uniform matroid , the four-point line.
[.][.][, Section 10.2, "An excluded minor criterion for a matroid to be binary", pp. 167–169.]
-
In the geometric lattice associated to the matroid, every interval of height two has at most five elements.
Related matroids
Every
regular matroid, and every
graphic matroid, is binary.
A binary matroid is regular if and only if it does not contain the
Fano plane (a seven-element non-regular binary matroid) or its dual as a
matroid minor.
[, Theorem 10.4.1, p. 175.] A binary matroid is graphic if and only if its minors do not include the dual of the graphic matroid of
nor of
.
[, Theorem 10.5.1, p. 176.] If every circuit of a binary matroid has odd cardinality, then its circuits must all be disjoint from each other; in this case, it may be represented as the graphic matroid of a
cactus graph.
Additional properties
If
is a binary matroid, then so is its dual, and so is every
matroid minor of
.
Additionally, the direct sum of binary matroids is binary.
define a bipartite matroid to be a matroid in which every circuit has even cardinality, and an [[Eulerian matroid]] to be a matroid in which the elements can be partitioned into disjoint circuits. Within the class of graphic matroids, these two properties describe the matroids of [[bipartite graph]]s and [[Eulerian graph]]s (not-necessarily-connected graphs in which all vertices have even degree), respectively. For [[planar graphs]] (and therefore also for the graphic matroids of planar graphs) these two properties are dual: a planar graph or its matroid is bipartite if and only if its dual is Eulerian. The same is true for binary matroids. However, there exist non-binary matroids for which this duality breaks down.[/]
Any algorithm that tests whether a given matroid is binary, given access to the matroid via an matroid oracle, must perform an exponential number of oracle queries, and therefore cannot take polynomial time.[.]
